package com.brett.frame.learn.sort.insert;

/**
 * 二分插入排序，
 * 对已排序列对半查找合适位置，减少比较次数
 * @author lenovo
 *
 */
public class HalfInsertSort {
	public int[] sort(int[] arr) {

		for (int i = 1; i < arr.length; i++) {
			if (arr[i - 1] > arr[i]) {
				int tmp = arr[i];
				int low = 0;
				int hight = i - 1;
				int mid = 0;
				// 二分查找
				while (low <= hight) {
					mid = (low + hight) / 2;
					if (tmp > arr[mid]) {
						low = mid + 1;
					} else {
						hight = mid - 1;
					}
				}
				System.out.println(i+"low:hight="+low+":"+hight);
				// hight之后的数据依次后移1位
				int j = i - 1;
				for (; j >= hight+1; j--) {
					arr[j + 1] = arr[j];
				}
				arr[j + 1] = tmp;
			}
		}
		return arr;
	}

}
